1. Field of the Invention
The present invention relates to a scheme for carrying out modular calculations, especially modular exponentiation calculations, which are necessary for basic operations and key generation in public key cryptosystems such as RSA cryptosystem.
2. Description of the Background Art
Basic operations and key generation in public key cryptosystems such as RSA cryptosystem require modular calculations such as modular exponentiation a.sup.b mod c, modular multiplication a.times.b mod c, and modular reduction a mod c. In addition, application protocols utilizing public key cryptosystems often utilize these modular calculations in combination. Consequently one frequently encounters cases where some modular calculation result is to be used in next calculation. In view of this fact, there has been a proposition of a calculation scheme using redundant binary calculation, as disclosed in A. Vandemeulebroecke, et al.: "A New Carry-Free Division Algorithm and its Application to a Single-Chip 1024-b RSA Processor", IEEE Journal of Solid-State Circuits, Vol. 25, No. 3, pp. 748-756, June 1990.
However, this conventional scheme has been associated with the problem that modular exponentiation a.sup.b mod c and modular reduction a mod c cannot be calculated when .vertline.a.vertline.&gt;.vertline.c.vertline.. In the following description, .vertline.k.vertline. will be referred to as a number of bits of k, and a, b and c appearing in modular exponentiation a.sup.b mod c will be referred to as mantissa (dividend), exponent, and modulus (divisor), respectively.
In principle, the redundant binary calculation requires the most significant bit of a divisor in binary expression to be "1" in a case of division, so that there has been a limitation that a number of bits of a divisor of a designed division circuit must coincide with a number of bits of a divisor to be used in calculation.
In this regard, there has been a proposition disclosed in Japanese Patent Application Laid Open No. 8-147266 (1996) for removing this limitation on a number of bits of a modulus by the following provisions.
(1) An entire divisor (modulus) is left shifted until the most significant bit of a divisor (modulus) becomes "1".
(2) An entire dividend (mantissa) is also left shifted as much as a shifting made in (1).
(3) A calculation is carried out by the conventional redundant binary calculation.
(4) A calculation result is right shifted as much as a shifting made in (1) in order to correct the calculation result.
However, since the mantissa is to be right shifted for the same number of bits as the modulus in (2), there has been a problem that an accurate calculation becomes impossible when a number of bits of the mantissa is larger than a number of bits of the modulus because of the overflow.
Under such condition, when an application of this proposition to LSI is considered, there is no problem when the mantissa is set to be smaller than the modulus in advance, but it is rather inconvenient for applications to various application programs. For example, in a case of modular multiplication a.times.b mod c, one usually has a&lt;c and b&lt;c but a product a.times.b becomes larger than c in general so that this calculation cannot be carried out by this proposition.
Now, the modular exponentiation is frequently utilized as basic operations in public key cryptosystems. For example, in RSA cryptosystem, modular exponentiation using a secret exponent is to be carried out in the decryption operation and the signing operation.
Conventionally, almost all public key cryptosystems utilize modular exponentiation, which can be expressed as a.sup.b mod c. In the signing operation or the decryption operation, at least one of the three parameters involved in modular exponentiation is to be kept secret.
However, when three parameters are exactly the same, an identical result will be obtained obviously. On the other hand, in a case of carrying out modular exponentiation using a dedicated processor, an identical calculation result is always obtained when an environment such as operation frequency is constant. Then, there is a report which points out that a secret key can be obtained by utilizing these features, as disclosed in P. C. Kocher: "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems", Advances in Cryptology--CRYPTO'96, Lecture Notes in Computer Science 1109, pp. 104-113, Springer-Verlag.
This method (called timing attack) is somewhat time consuming and not very easy, but still far easier than a method for deriving a secret key by utilizing mathematical features or a method for carrying out the extensive search of a secret key. This method becomes more dangerous in an environment in which the time can be measured more accurately. Moreover, this method becomes more dangerous when a number of parallel jobs is fewer.
Thus, the secret key calculation utilizing modular exponentiation and the like has the same amount of calculations for exactly the same parameters, and there are cases where this feature can be maliciously utilized to obtain a secret key.